/*
CCP 4.3
Given a sorted (increasing order) array, write an algorithmto 
create a binary search tree with minimal height.
*/
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;

struct NodeQuintiq
{
	int val;
	Node* left;
	Node* right;
	Node(int v):val(v),left(NULL),right(NULL){}
};

Node* Array2BST(int a[],int start,int end)
{
	if(start > end)
		return NULL;
	int mid = start + ((end - start)>>1);
	Node* root = new Node(a[mid]);
	root->left = Array2BST(a,start,mid-1);
	root->right = Array2BST(a,mid+1,end);
	return root;
}

void levelOrder(Node* root)
{
	if(!root)return;
	queue<Node*> que;
	que.push(root);
	while(!que.empty())
	{
		Node* cur = que.front();
		que.pop();
		cout<<cur->val<<" ";
		if(cur->left)
			que.push(cur->left);
		if(cur->right)
			que.push(cur->right);
	}
}
int main()
{
	int a[]={1,2,3,4,5,6};
	Node* root = Array2BST(a,0,5);
	levelOrder(root);

	return 0;
}